//
// Created by Administrator on 2021/8/4.
//
//给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <string>

using namespace std;

class Solution {
public:
    /**
     * 暴力：o(n^3)
     * 任意两边之和大于第三边
     * 从最大边c开始遍历
     * 需要在前面的边中，找到能使得 a + b > c 成立的 a 、b
     * @param nums
     * @return
     */
    int triangleNumber(vector<int> &nums) {
        // 先排序
        sort(nums.begin(), nums.end());
        int ans = 0;
        for (int i = (int)nums.size() - 1; i >= 0; --i) {
            // 以nums[i]为最长的边c
            // 在0 到 i-1 中找 合适的a b
            // 问题就变成：从一个有序数列中，找到两数之和大于nums[i]的组合数
            int left = 0, right = i - 1;
            while (left < right) {
                if (nums[left] + nums[right] <= nums[i]) {
                    ++left;
                } else {
                    // 此时 左右点之和大于nums[i]
                    // 那么，最右点right  和 left ~right-1 之间的组合都是满足的
                    ans += right - left;
                    --right;  // 移动指针
                }
            }
        }
        return ans;
        // 通过
    }
};

int main() {
    vector<int> nums{2, 2, 3, 4};
    vector<int> nums2{4, 2, 3, 4};
    vector<int> nums3{4};
    Solution solution;
    cout << solution.triangleNumber(nums) << endl;
    cout << solution.triangleNumber(nums2) << endl;
    cout << solution.triangleNumber(nums3) << endl;
    return 0;
}
